# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def sortList(self, head: ListNode) -> ListNode:

        def nodeSort(head: ListNode, tail: ListNode) -> ListNode:
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return merge(nodeSort(head, mid), nodeSort(mid, tail))

        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            result = ListNode(0)
            p, p1, p2 = result, head1, head2
            while p1 and p2:
                if p1.val < p2.val:
                    p.next = p1
                    p1 = p1.next
                    p = p.next
                else:
                    p.next = p2
                    p2 = p2.next
                    p = p.next
            if p1:
                p.next = p1
            else:
                p.next = p2
            return result.next
        return nodeSort(head, None)


if __name__ == '__main__':
    x = Solution()
    t = ListNode(3)
    t.next = ListNode(2)
    t.next.next = ListNode(1)
    x.sortList(t)
    print()
